Computer operating systems require memory to store data related to operating system functions. Relocation of data from one physical memory location to another is sometimes necessary. For example, if one memory board begins to fail, it might be desirable to replace it. In addition, in a distributed computing system, it is sometimes helpful to migrate a process from one processor to another, for example, so that the process is closer to resources being accessed by the process. When a process is migrated, it can reduce latency and bus traffic if the data being accessed by the processor is located on the same board or otherwise close to the processor executing the process.
A portion of a computer's memory is allocated to the operating system kernel. The kernel memory is allocated from the main memory of the system and is generally partitioned into relocatable pages of kernel memory and non-relocatable (NR) pages of kernel memory. Data that is designated NR by the kernel is stored in NR kernel memory pages.
Modern computers provide each process being executed in a computer system, including the kernel, its own virtual address space. This allows memory to be dynamically allocated to each running process while at the same time providing all the running processes with contiguous address space. Virtual address spaces also allows a process to use more memory than is physically available in the system by paging little-accessed data to secondary storage. In many cases, a single page of physical memory is shared by a plurality of processes, each having a different VA that references that physical page.
A page of memory is the smallest unit of memory that can be allocated or mapped. The computer operating system and hardware work together to map the virtual addresses assigned to each process to corresponding physical pages thereby making the appropriate location in memory available when needed by a process. Page size can be fixed for all processes, or may vary from process to process. For example, if the physical page size is 8 kilobytes, a process can request or be directed to use virtual page sizes of multiples of 8K, e.g., 8K, 64K, 512K, 4M, 32M, 256M, 2 G, and 16 G. The use of user-defined page sizes can permit an application to optimize performance. Larger page sizes can reduce translation buffer miss rates while smaller page sizes can improve the utilization efficiency of the memory.
Relocating memory being accessed by its corresponding VA requires only that the mappings be updated to reflect the new physical address of the data after it is relocated. However, there are situations in which data is accessed using its physical address (PA) which can make relocating the data more difficult. For example, direct memory access (DMA) allows certain hardware or software subsystems within a computer to directly access system memory for reading and/or writing independently of the processor or processors. Many subsystems use DMA including secondary storage controllers, display interfaces, and network interfaces. In a DMA transfer, a block of memory is copied from one device to another. While a processor may initiate the transfer, the transfer itself is performed by a DMA controller. Since DMA bypasses the processor, which is responsible for performing VA to PA translations, the DMA controller accesses system memory using the physical address of the memory, not a virtual address. As a result, some device drivers may require allocations of NR kernel memory. This prevents the data from being moved during DMA transfers. The kernel will also store NR data such as the kernel stack and text in the NR partition of the kernel memory.
If relocatable kernel memory becomes full, it is possible to store relocatable data in the NR kernel memory partition. However, there then exists a need to move relocatable data to the relocatable kernel memory partition if more space in the NR partition is needed.
To identify relocatable data in an NR region of kernel memory, related U.S. patent application Ser. No. 10/838,495, filed May 3, 2004, proposes partitioning the kernel virtual address space into relocatable and nonrelocatable regions. In that application, relocatable data is always assigned a virtual address in the relocatable partition of the virtual address space. Thus, when relocatable data is stored in the NR partition, it can be identified by its virtual address, which would remain in the relocatable partition of the virtual address space.
This solution works well for systems having a 64 bit address space. However, in systems having 32 bit addresses, such as the popular x86 architectures, partitioning the virtual address space imposes a burdensome artificial restriction on the memory. Furthermore, even in a 64 bit environment, identifying the virtual address of a physical page for the purpose of determining whether a particular page of data is relocatable or not can be an inefficient procedure.
Therefore, there exists a need to efficiently identify which pages in nonrelocatable memory contain relocatable data without placing artificial restrictions on the kernel's virtual address space, so that, if necessary, nonrelocatable memory may be freed by moving the relocatable data to the relocatable kernel memory partition.